﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.StackAndQueue
{
    //=========================力扣232 用栈实现队列
    //请你仅使用两个栈实现先入先出队列。
    //队列应当支持一般队列支持的所有操作（push,pop,peek,empty）
    //void push(int x)将元素x推到队列末尾
    //void pop()从队列的开头移除并返回元素
    //int peek()返回队列开头的元素
    //boolean empty()如果队列为空，返回true，否则返回false。
    //只能使用标准栈操作，也就是只有push to top,peek/pop from top,size和is empty操作是合法的
    //如果语言不支持栈，可以使用list或者deque(双端队列）来模拟一个栈
    //能否实现每个操作均摊时间复杂度为O(1)。
    class MyQueue
    {
        //思路：进入队列的时候，直接将元素压入输入栈即可
        //出队列的时候，将输入栈的栈顶元素压入输出栈，这样元素就反过来了，然后再弹出输出栈的栈顶元素即可

        private Stack<int> stIn;
        private Stack<int> stOut;

        public MyQueue()
        {
            stIn = new Stack<int>();
            stOut = new Stack<int>();
        }

        //将元素x推到队列末尾
        public void Push(int x)
        {
            //直接推入到输入栈
            stIn.Push(x);
        }

        //从队列的开头移除并返回元素
        public int Pop()
        {
            //当输出栈为空的时候，往里导入输入栈的数据
            if(stOut.Count == 0)
            {
                while(stIn.Count != 0)
                {
                    stOut.Push(stIn.Pop());
                }
            }
            return stOut.Pop();
        }

        //返回队列开头的元素
        public int peek()
        {
            int res = Pop();//使用已有的pop函数
            stOut.Push(res);//因为弹出了res，所以再添加回去
            return res;
        }
        public bool Empty()
        {
            return stOut.Count == 0 && stIn.Count == 0;
        }
    }
}
